// https://www.lintcode.com/problem/unique-paths/my-submissions

class Solution {
public:
    /**
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    // int uniquePaths(int m, int n) {
    //     // 注意格子和数组的对应
    //     vector<vector<int>> result(m, vector<int>(n, 0));
    //     for (int i = 0; i < m; ++i)
    //     {
    //         // result[m][0] = 1; 检查了好久！！！
    //         result[i][0] = 1;
    //     }
    //     for (int i = 0; i < n; ++i)
    //     {
    //         result[0][i] = 1;
    //     }
    //     for (int i = 1; i < m; ++i)
    //     {
    //         for (int j = 1; j < n; ++j)
    //         {
    //             result[i][j] = result[i - 1][j] + result[i][j - 1];
    //         }
    //     }
    //     return result[m - 1][n - 1];
    // }
    
    // 反正顺序对，初始化可以放到for循环里
    int uniquePaths(int m, int n) {
        vector<vector<int>> result(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (i == 0 || j == 0)
                    result[i][j] = 1;
                else
                    result[i][j] = result[i - 1][j] + result[i][j - 1];
            }
        }
        return result[m - 1][n - 1];
    }
};